package basic_datastructure.tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

public class UnrecurPreInPostTraversal {
    public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(new Integer[]{
                3, 2, 9, null, null, 10, null, null, 8, null, 4
        }));
        TreeNode binaryTree = createBinaryTree(inputList);
        System.out.print("前序遍历：");
        unrecurPreOrderTraversal(binaryTree);
        System.out.println();
        System.out.print("中序遍历：");
        unrecurInOrderTraversal(binaryTree);
    }

    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        if (inputList == null || inputList.isEmpty()) {
            return null;
        }
        TreeNode node = null;
        Integer data = inputList.removeFirst();
        if (data != null) {
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }

    /**
     * 先序遍历的非递归方法：
     * 先序遍历顺序：根、左、右，所以入栈顺序为先右 后左，出栈就变成 先左 后右
     *
     * @param root 传入根节点
     */
    public static void unrecurPreOrderTraversal(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            //现将根节点入栈
            stack.push(root);
            //栈不为空
            while (!stack.isEmpty()) {
                //从栈中弹出，并打印
                TreeNode node = stack.pop();
                System.out.print(node.data + " ");
                //先右后左(如果存在)
                if (node.rightChild != null) {
                    stack.push(node.rightChild);
                }
                if (node.leftChild != null) {
                    stack.push(node.leftChild);
                }
            }
        }
    }

    public static void unrecurPostOrderTraversal(TreeNode root) {
        if (root != null) {
            //用来存节点
            Stack<TreeNode> stack1 = new Stack<>();
            //用来逆序打印顺序
            Stack<TreeNode> stack2 = new Stack<>();
            stack1.push(root);
            while (!stack1.isEmpty()) {
                TreeNode node = stack1.pop();
                stack2.push(node);
                if (node.leftChild != null) {
                    stack1.push(node.leftChild);
                }
                if (node.rightChild != null) {
                    stack1.push(node.rightChild);
                }
            }
            while (!stack2.isEmpty()) {
                System.out.print(stack2.pop().data + " ");
            }
        }
    }

    public static void unrecurInOrderTraversal(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode curNode = root;
            while (!stack.isEmpty() || curNode != null) {
                if (curNode != null) {
                    stack.push(curNode);
                    curNode = curNode.leftChild;
                }else {
                    curNode = stack.pop();
                    System.out.print(curNode.data);
                    curNode = curNode.rightChild;
                }
            }
        }
    }
}